#lang racket
;Merge-sort(Сортировка слиянием)
(define(merge-sort lst)
   (cond 
     [(small lst) lst]
     [(merge-lists(merge-sort(left-half lst))(merge-sort(right-half lst)))]))
 
(define(small lst)
   (or(empty? lst)(empty?(cdr lst))))

(define(right-half lst)
   (drop lst(ceiling(/(length lst)2)))) ; отбрасывает первые n элементов 

(define(left-half lst)
   (take lst(ceiling(/(length lst)2)))) ; берет первые n элементов 

(define(merge-lists left right) ; left, right изначально отсортированы по возрастанию
  (cond 
    [(and (cons? left)(cons? right)) 
      (cond 
        [(<= (car left)(car right)) (cons (car left) (merge-lists (cdr left) right))]
        [(cons (car right)(merge-lists left (cdr right)))])]
    [(cons? left) left ] ; cons? - не пустой.
    [else right]
  )
)